COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input lisp.tex[206,lsp]  % TEX file, used in the soln for Problem Set 3
C00005 00003	\HeadA⊂Answers to Problem Set $\#$3 - Due April 26, 1979⊃
C00009 00004	\QUEST $3$ ([MT]p29 $\#1$).
C00015 00005	\QUEST $5$.
C00017 00006	\QUEST $6$.
C00020 00007	\par\vfill\eject
C00021 00008	% This was printed, as is...
C00023 ENDMK
C⊗;
\input lisp.tex[206,lsp]  % TEX file, used in the soln for Problem Set 3
	% Spring 1979
% This is the answer to the homework set # 3 
% Handed out: Thursday 12-April; due Thursday 19-April
\HeadA⊂Answers to Problem Set $\#$3 - Due April 26, 1979⊃

\QUEST $1$ ([MT]p25 $\#1$).
$$\vcenter{\halign{\lft{\LISPE#|}⊗\lft{\LISPE (TIMES #|}⊗\lft{\LISPE # |}⊗\lft{\LISPE #|}\cr
$\biglp$PLUS ⊗\funct diff[X,X] ⊗(PLUS Y 1)⊗3)\cr
⊗X⊗\funct diff[(PLUS Y 1),X]⊗3)\cr
⊗X⊗(PLUS Y 1)⊗\funct diff[3,X])$\bigrp$\cr
}}$$
This equals
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE (TIMES#|}⊗\lft{\LISPE # |}⊗\lft{\LISPE #|}\cr
$\biglp$PLUS ⊗1⊗(PLUS Y 1)⊗3)\cr
⊗X⊗(PLUS \funct diff[Y,X] \funct diff[1,X])⊗3)\cr
⊗X⊗(PLUS Y 1)⊗0$\bigrp$\cr}}$$
or
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE (TIMES#|}⊗\lft{\LISPE # |}⊗\lft{\LISPE #|}\cr
$\biglp$PLUS ⊗1⊗(PLUS Y 1)⊗3)\cr
⊗X⊗(PLUS 0 0)⊗3)\cr
⊗X⊗(PLUS Y 1)⊗0$\bigrp$\cr
}}$$
If we had an algebraic simplifier which knew about standard operations, such as
\LISPI (TIMES 1 {\rm x}) \eq {\rm x} \eq (PLUS 0 {\rm x})|,
this would reduce to
\LISPI (PLUS (TIMES (PLUS Y 1) 3) (TIMES X 0 3) (TIMES X (PLUS Y 1) 0)) \eq
(PLUS (TIMES (PLUS Y 1) 3) 0 0) \eq
(TIMES (PLUS Y 1) 3)|, as we would expect.

\QUEST $2$ ([MT]p25 $\#2$).
We will use the LISP simplification process of writing only  
``x'' whenever we encounter
\LISPI (T $∧$ {\rm x})| or \LISPI (NIL $∨$ {\rm x})|,
and stopping the computation,  simply returning 
$↑{(1)}$\LISPI NIL| if \LISPI (NIL $∧$ {\rm x})| is found, 
or $↑{(2)}$\LISPI T| for \LISPI (T $∨$ {\rm x})|.
So
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
\funct orlis[\at{},{\LISPE ((A B) (C D) E)|}]⊗
\eq $~$\n {\LISPE ((A B) (C D) E)|} $\null ∨\null$\cr
⊗\qquad\qquad [\at{\a{\LISPE ((A B) (C D) E)|}}
$∧$ \funct orlis[\at{},\d{\LISPE ((A B) (C D) E)|}]]\cr
⊗\eq T $∧$ [\at{\LISPE (A B)|} $∨$ \funct orlis[\at{},{\LISPE ((C D) E)|}]]\cr
⊗\eq [NIL $∨$ \funct orlis[\at{},{\LISPE ((C D) E)|}]]\cr
⊗\eq \funct orlis[\at{},{\LISPE ((C D) E)|}]\cr
⊗\eq $~$\n {\LISPE ((C D) E)|} $∧$ [\at{\a{\LISPE ((C D) E)|}}
$∨$ \funct orlis[\at{},\d{\LISPE ((C D) E)|}]]\cr
⊗\eq T $∧$ [\at{\LISPE (C D)|} $∨$ \funct orlis[\at{},{\LISPE (E)|}]]\cr
⊗\eq [NIL $∨$ \funct orlis[\at{},{\LISPE (E)|}]]\cr
⊗\eq \funct orlis[\at{},{\LISPE (E)|}]\cr
⊗\eq $~$\n {\LISPE (E)|} $∧$ [\at{\a{\LISPE (E)|}}
$∨$ \funct orlis[\at{},\d{\LISPE (E)|}]]\cr
⊗\eq T $∧$ [\at{\LISPE E|} $∨$ \funct orlis[\at{},{\LISPE ()|}]]\cr
⊗\eq [T $∨$ \funct orlis[\at{},{\LISPE ()|}]]\cr
⊗\eq T\cr}}$$
\QUEST $3$ ([MT]p29 $\#1$).
This \LISPE eval| function makes several assumptions. One is that the
list \LISPI a| will hold all the appropriate values we will need.
We should check if this assumption might be violated:
\LISPE \d{\funct assoc[e,a]}| is investigated on the second line.
Better would be
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
[[\λ x:\if {\n x}⊗\then \funct ERROR[``Unable to identify constant '',e ]\cr
⊗\else \d x]\cr
\quad\funct assoc[e,a]]⊗\cr
}}$$
Similarly, the $12↑{th}$ line should be changed from the na{\"\i}ve 
$$\vcenter{\halign{{\LISPE #|}\cr
$\ldots$ \funct eval[ \cons ⊂\d{\funct assoc[\a e,a]}.\d e⊃, a]\cr
}}$$
to 
$$\vcenter{\halign{{#}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
$\ldots$⊗[[\λ x:\if \n x ⊗\then \funct ERROR[``Unable to identify function '',\a e ]\cr
⊗⊗\else \funct eval[ \cons ⊂\d x.\d e⊃, a]]\cr
⊗\funct assoc[\a e,a]]\cr
}}$$

Scanning through this list of \elseif{}s,
we see a number of \LISPI \a{\d e}|'s.
Before each, a check should be made that \LISPI \d e| is not an atom.
When the operator is monadic, \LISPI \n \d{\d e}| should be true as well.
For the binary operators CONS and EQ,
\LISPI \d{\d e}| must be non-atomic
and \LISPI \d{\d{\d e}}| must be \LISPI NIL|.
Similar checks that \LISPI \d{\a{\a e}}| should be made before computing
\LISPI \a{\d{\a{\a e}}}| in the $13↑{th}$ in the $14↑{th}$ lines.
In each case, an error message pointing out this malformed list should be issued,
possibly specifying just what was expected, and what was found.

Finally, we need to worry about the case when the \a{} part of a list is
a function, which returns a function name,
or a \LISPI LAMBDA| or  \LISPI LABEL| form.
For example, if \LISPE \funct DUMB[] \assign 'PLUS|, then we would like
\LISPI ( (DUMB) 2 3)| to succeed, returning
\LISPI (PLUS 2 3)| or $5$.
To do this, we need to add a $15↑{th}$ line, which computes
\LISPI $\ldots$ \else \funct eval[ {\cons ⊂\funct eval[ \a e, a].\d e⊃},a]|.

The auxilary functions
\LISPI evcond|, \LISPI evlist|, and \LISPI prup| should have checks as well.
\LISPI evcond| should check that \LISPI \a{\a u}| exists before using it,
and if it exists,
(especially when it is  non-\LISPI NIL|,) \LISPI \d{\a u}| must be non-atomic.
In \LISPI prup|, we assume 
\LISPI u| and \LISPI v| are the same length. 
Replacing the 
\disptext{\LISPE $\ldots$ \if \n u \then NIL \else $\ldots$|
}
with
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
$\ldots$ \if (\n u $∧$ \n v) ⊗\then NIL⊗\cr
⊗\else \if (\at u $∨$ \at v) ⊗\then \funct ERRORS[``Lists not sam→ length '',(\cons ⊂u.v⊃)]\cr
⊗⊗\else $\ldots$\cr
}}$$
would insure this.

This \LISPE ERRORS| function printout out an error message (its arguments),
and halts the computation. More complex versions might ask the user to replace
the value of the offending argument.

\QUEST $4$ ([MT]p29 $\#2$).
We should add the following lines, after line $11$:\par
$$\vcenter{\halign{\lft{\LISPI \else \if \a e \eq # |}⊗\lft{\LISPI \then #|}\cr
OR⊗\funct evor[\d e,a]\cr
AND⊗\funct evand[\d e,a]\cr
NOT⊗\n {\funct eval[\a{\d e},a]}\cr
}}$$
where
$$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
\funct evor[u,a] \assign⊗\if \n u ⊗\then NIL\cr
⊗⊗\else \funct eval[ \a u,a ] $∨$ \funct evor[\d u,a]\cr
\funct evand[u,a] \assign⊗\if \n u ⊗\then T\cr
⊗⊗\else \funct eval[ \a u,a ] $∧$ \funct evand[\d u,a]\cr
}}$$

As demonstrated by the prior problem, there are many places where error checks
could be inserted.
\QUEST $5$.
Calling \LISPI (DIAGNOSES PATIENTS DISEASES)| should return\par
\vskip6pt
\hbox to size{\hfill$\left(\hskip6pt\vcenter{
{\halign{\lft{\LISPI (# |}⊗\lft{\LISPI #)|}\cr
RDG⊗FAIL-LISP-CLASS INSANITY HEALTHY\cr
DBL⊗HEALTHY\cr
BCM⊗LACONIC-NESS FEAR-OF-FRYING\cr
CLEOPATRA⊗CHICKEN-POX\cr
DOLLAR⊗FAIL-LISP-CLASS MIDAS-TOUCH INSANITY\cr
ICARUS⊗FEAR-OF-FLYING HEALTHY\cr
FISHER⊗CHESS-ITIS HEALTHY\cr
PAULING⊗HAYFEVER\cr
BIGMOUTH⊗FAIL-LISP-CLASS VERBOSITY INSANITY HEALTHY\cr
BIGMOUTH2⊗FAIL-LISP-CLASS LACONIC-NESS INSANITY HEALTHY\cr
NOTHING⊗HEALTHY\cr
DIRTYNEEDLE⊗HEPATITUS\cr
SMALLTALK⊗LACONIC-NESS HEALTHY\cr
ROBBERBARON⊗GERMAN-MEASLES\cr
SICKIE⊗\cr
MRHANGOVER⊗TOOTHACHE STOMACHACHE\cr
}}
}\hskip6pt\right)$\hfill}
\vskip6pt
The final page shows an example of an acceptable set of programs for 
computing this \LISPI DIAGNOSES| function.
\par
\eject
\QUEST $6$.
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
\funct LND[ u,n ]⊗\assign \funct LND1[ u,n,0 ]⊗\cr
\funct LND1[ u,n,m ]⊗\assign \if \n u⊗\then \if \funct zerop[ m ] \then T \else NIL\cr
⊗⊗\qquad {\rm; The value of }\funct length[u] $-$ m $\modop$ n 
{\rm is invariant}\cr
⊗⊗\else \funct LND1[ \d u, n,
{\funct SUB1[ \if {\funct zerop[ m ]} \then n \else m ]}]\cr
}}$$

\QUEST $7$\ (Optional).
$$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr
\funct LND[ u,n ]⊗\assign \if (\funct FIXP[ n ] ⊗$\null∧$ n$>$0)
⊗\then \funct LND1[ u,n,0 ]\cr
⊗⊗⊗\else \funct ERROR[``Expected a Positive Integer, not '',n]\cr
\funct LND1[ u,n,m ]⊗\assign \if \n u⊗\then{}⊗\if \funct zerop[ m ] \then T
\else NIL\cr
⊗⊗\elseif{}⊗\at u \then \funct ERROR[``Expected a LIST, not '', u]\cr
⊗⊗\else{}⊗\funct LND1[ \d u,n,
{\funct SUB1[ \if {\funct zerop[ m ]} \then n \else m ]}]\cr
}}$$
\NOTE This \LISPI ERROR| function will always return \LISPI NIL|.\eton
\par\vfill\eject
\end
% This was printed, as is...

(DEFUN DIAGNOSES (PATIENTS DISEASES) 
       (MAPCAR 
	'(LAMBDA (X) (CONS (CAR X) (INDIVDIAG (CDR X) DISEASES)))
	PATIENTS)) 

(DEFUN INDIVDIAG (PAT DIS) 
       (COND ((NULL DIS) NIL)
	     ((HASDIS PAT (CADAR DIS) (CADDAR DIS))
	      (CONS (CAAR DIS) (INDIVDIAG PAT (CDR DIS))))
	     (T (INDIVDIAG PAT (CDR DIS))))) 

(DEFUN HASDIS (P MUST MUSTNOT) 
       (AND (ANDLIS '(LAMBDA (X) (NOT (MEMBER X P))) MUSTNOT)
	    (ANDLIS '(LAMBDA (X) (MEMBER X P)) MUST))) 

(DEFUN ANDLIS (F X) 
       (COND ((NULL X) T)
	     (T (AND (FUNCALL F (CAR X)) (ANDLIS F (CDR X))))))